package com.longge;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-03-07 23:09
 */
public class LevelOrderII {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        dfs(root, res, 0, true);
        return res;
    }

    private void dfs(TreeNode root, List<List<Integer>> res, int i, boolean b) {
        if (root == null) return;
        if (res.size() == i) {
            res.add(new LinkedList<>());
        }
        dfs(root.left, res, i+1, !b);
        dfs(root.right, res, i+1, !b);
        LinkedList<Integer> subRes = (LinkedList<Integer>) res.get(i);
        if (b){
            subRes.offer(root.val);
        }else {
            subRes.push(root.val);
        }
    }
}
